Không rõ năm xây dựng, chỉ biết ban đầu ngôi đình được dựng bằng bằng tre lá đơn sơ tọa lạc ở phường Vĩnh Nguơn, để thờ Nguyễn Hữu Lễ (? - ?), một người dân tại địa phương (có nguồn ghi là trưởng thôn), không rõ thân thế.

Tương truyền, ông đã đứng ra huy động dân làng, tập hợp thuyền bè để đưa chúa Nguyễn Phúc Ánh và đoàn tùy tùng vượt sông chạy trốn khi bị quân Tây Sơn truy đuổi. Sau đó, ông cùng mọi người nhận chìm hết xuồng ghe. Không có phương tiện để đuổi theo, quân Tây Sơn bèn trút mọi tức giận lên dân làng. Để cứu mọi người, ông đã can đảm đứng ra nhận tội chủ mưu và bị xử chết [1]. Cảm khái nghĩa khí của ông, người dân đã lập nơi thờ phụng để hương khói tưởng nhớ.

Năm 1802, nhà Tây Sơn bị đánh đổ, chúa Nguyễn Phúc Ánh lên ngôi vua xưng là Gia Long. Nhớ công lao của ông, nhà vua bèn sắc phong ông làm "Thành Hoàng Nghĩa Dũng Hữu Lễ Nguyễn Công Tôn Thần", ban tặng tấm liễn "Nghĩa khí trung hưng", đồng thời cấp cho sở đất thu huê lợi, để trùng tu đình thờ và tổ chức lễ cúng vía hàng năm. Đến đời vua Khải Định năm thứ 9 (1924), lại gia phong ông làm "Đoan Túc Dực Bảo Trung Hưng Tôn Thần".

Năm 1929, Đốc phủ Trương Tấn Vị cùng Ban quý tế họp sức dời ngôi đình về địa điểm hiện nay, vì chỗ cũ hằng năm thường xuyên bị ngập vào mùa nước nổi. Lúc ấy, ngôi đình cũng được làm mới hoàn toàn vì cây lá cũ đã bị hư hỏng. Mái được lợp ngói, vách được xây gạch, các cột được thay bằng gỗ căm xe... Ngoài chính điện, họ còn xây dựng võ qui, võ ca, nhà khói, cổng ra vào...Về sau, đình Vĩnh Nguơn còn được tu sửa nhiều lần, nhưng đến nay vẫn còn giữ được dáng vẻ của lần kiến tạo này.